#include "odd-even.h.pob"
#include <cstdlib>

OddEven::Worker::Worker(unsigned int _i, unsigned int _n) : Sorter::Worker(_i, _n) { }

int IncOrder(const void *e1, const void *e2)  { 
  return (*((int *)e1) - *((int *)e2)); 
}
/* This is the CompareSplit function */ 
void OddEven::Worker::CompareSplit(int nlocal, int *elmnts, int *relmnts, int *wspace,int keepsmall)  { 
  int i, j, k; 

  for (i=0; i<nlocal; i++) 
    wspace[i] = elmnts[i]; /* Copy the elmnts array into the wspace array */ 

  if (keepsmall) { /* Keep the nlocal smaller elements */ 
    for (i=j=k=0; k<nlocal; k++) { 
      if (j == nlocal || (i < nlocal && wspace[i] < relmnts[j])) 
	elmnts[k] = wspace[i++]; 
      else 
	elmnts[k] = relmnts[j++]; 
    } 
  } 
  else { /* Keep the nlocal larger elements */ 
    for (i=k=nlocal-1, j=nlocal-1; k>=0; k--) { 
      if (j == 0 || (i >= 0 && wspace[i] >= relmnts[j])) 
	elmnts[k] = wspace[i--]; 
      else 
	elmnts[k] = relmnts[j--]; 
    } 
  } 
}

void OddEven::Worker::sort() {
	int nn;         /* The total number of elements to be sorted */ 
	int npes;      /* The total number of processes */ 
	int myrank;    /* The rank of the calling process */ 
	int nlocal;    /* The local number of elements, and the array that stores them */ 
	int *elmnts;   /* The array that stores the local elements */ 
	int *relmnts;  /* The array that stores the received elements */ 
	int oddrank;   /* The rank of the process during odd-phase communication */ 
	int evenrank;  /* The rank of the process during even-phase communication */ 
	int *wspace;   /* Working space during the compare-split operation */ 
	int j; 
  MPI_Status status; 
  
  
	nn = size;
	nlocal = nn/npes; /* Compute the number of elements to be stored locally. */ 
  
  /* Allocate memory for the various arrays */ 
	elmnts  = (int *)malloc(nlocal*sizeof(int));
	relmnts = (int *)malloc(nlocal*sizeof(int)); 
	wspace  = (int *)malloc(nlocal*sizeof(int));
  
  /* Fill-in the elmnts array with random elements */ 
  srand(i);
  for (j=0; j<nlocal; j++) 
    elmnts[j] = random(); 
  
  /* Sort the local elements using the built-in quicksort routine */ 
	std::qsort(elmnts, nlocal, sizeof(int), IncOrder); 
  
  /* Determine the rank of the processors that myrank needs to communicate during */ 
  /* the odd and even phases of the algorithm */ 
  if (myrank%2 == 0) { 
    oddrank  = myrank-1; 
    evenrank = myrank+1; 
  } 
  else { 
    oddrank  = myrank+1; 
    evenrank = myrank-1; 
  } 

  /* Set the ranks of the processors at the end of the linear */ 
  if (oddrank == -1 || oddrank == npes) 
    oddrank = -1; 
  if (evenrank == -1 || evenrank == npes) 
    evenrank = -1; 

  /* Get into the main loop of the odd-even sorting algorithm */ 
  for (j=0; j<npes-1; j++) { 
    if (j%2 == 1) { /* Odd phase */ 
			if(oddrank != -1) {
//				MPI_Isend(elmnts, nlocal, MPI_INT, oddrank, 1, MPI_COMM_WORLD, &request);
//				MPI_Recv( elmnts, nlocal, MPI_INT, oddrank, 1, MPI_COMM_WORLD, &status);
				comm->isend<Worker>(oddrank, elmnts, nlocal, 1);
				comm->receive<Worker>(oddrank, elmnts, nlocal, 1, &status);
			}
		}
    else /* Even phase */ {
			if(evenrank != -1) {
//				MPI_Isend(elmnts, nlocal, MPI_INT, evenrank, 1, MPI_COMM_WORLD, &request);
//				MPI_Recv( elmnts, nlocal, MPI_INT, evenrank, 1, MPI_COMM_WORLD, &status);
				comm->isend<Worker>(evenrank, elmnts, nlocal, 1);
				comm->receive<Worker>(evenrank, elmnts, nlocal, 1, &status);
			}
		}
    CompareSplit(nlocal, elmnts, relmnts, wspace,myrank < status.MPI_SOURCE); 
  } 

  free(elmnts); free(relmnts); free(wspace); 
}
